#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int BTDataType;

typedef struct BinaryTreeNode {
    BTDataType data;
    struct BinaryTreeNode *left;
    struct BinaryTreeNode *right;
} BTNode;

//类型
typedef BTNode *QDataType;
// 链式结构：表示队列
typedef struct QueueNode {
    QDataType data;
    struct QueueNode *next;
} QueueNode;
// 队列的结构
typedef struct Queue {
    QueueNode *head;
    QueueNode *tail;
} Queue;

// 初始化队列
void QueueInit(Queue *que) {
    assert(que);
    que->head = que->tail = NULL;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue *que) {
    assert(que);
    return que->head == NULL && que->tail == NULL;
}

// 队尾入队列
void QueuePush(Queue *que, QDataType data) {
    assert(que);
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    if (newNode == NULL) {
        perror("malloc fail:");
    } else {
        newNode->next = NULL;
        newNode->data = data;
    }
    if (que->head == NULL) {
        que->head = que->tail = newNode;
    } else {
        que->tail->next = newNode;
        que->tail = que->tail->next;
    }
}

// 队头出队列
void QueuePop(Queue *que) {
    assert(que);
    assert(!QueueEmpty(que));
    if (que->head->next == NULL) {
        free(que->head);
        que->head = que->tail = NULL;
    } else {
        QueueNode *next = que->head->next;
        free(que->head);
        que->head = next;
    }
}

// 获取队列头部元素
QDataType QueueFront(Queue *que) {
    assert(que);
    assert(!QueueEmpty(que));
    return que->head->data;
}

// 销毁队列
void QueueDestroy(Queue *que) {
    assert(que);
    QueueNode *curr = que->head;
    while (curr) {
        QueueNode *del = curr;
        curr = curr->next;
        free(del);
    }
    que->head = que->tail = NULL;
}

// 层序遍历
void TreeLevelOrder(BTNode *root) {
    Queue q;
    QueueInit(&q);
    if (root) {
        QueuePush(&q, root);
    }

    while (!QueueEmpty(&q)) {
        BTNode *front = QueueFront(&q);
        QueuePop(&q);
        printf("%d ", front->data);

        // 下一层，入队列
        if (front->left) {
            QueuePush(&q, front->left);
        }

        if (front->right) {
            QueuePush(&q, front->right);
        }
    }
    printf("\n");

    QueueDestroy(&q);
}

int main() {

    return 0;
}


